Expander Mixing Lemma

The expander mixing lemma intuitively states that the edges of certain $d$-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets $S$ and $T$ is always close to the expected number of edges between them in a random $d$-regular graph, namely $\frac dn, S, , T,$.

''d''-Regular Expander Graphs

Define an $(n, d, \lambda)$-graph to be a $d$-regular graph $G$ on $n$ vertices such that all of the eigenvalues of its adjacency matrix $A_G$ except one have absolute value at most $\lambda.$ The $d$-regularity of the graph guarantees that its largest absolute value of an eigenvalue is $d.$ In fact, the all-1's vector $\mathbf1$ is an eigenvector of $A_G$ with eigenvalue $d$, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of $G$ in absolute value.

If we fix $d$ and $\lambda$ then $(n, d, \lambda)$-graphs form a family of expander graphs with a constant spectral gap.

Statement

Let $G = (V, E)$ be an $(n, d, \lambda)$-graph. For any two subsets $S, T \subseteq V$, let $e(S, T) = , \,$ be the number of edges between ''S'' and ''T'' (counting edges contained in the intersection of ''S'' and ''T'' twice). Then

:$\left, e(S, T) - \frac\ \leq \lambda \sqrt\,.$

Tighter Bound

We can in fact show that

:$\left, e(S, T) - \frac\ \leq \lambda \sqrt\,$

using similar techniques.

Biregular Graphs

For biregular graphs, we have the following variation, where we take $\lambda$ to be the second largest eigenvalue.

Let $G = (L, R, E)$ be a bipartite graph such that every vertex in $L$ is adjacent to $d_L$ vertices of $R$ and every vertex in $R$ is adjacent to $d_R$ vertices of $L$. Let $S \subseteq L, T \subseteq R$ with $, S, = \alpha, L,$ and $, T, = \beta , R,$. Let $e(G) = , E(G),$. Then

:$\left, \frac - \alpha \beta\ \leq \frac \sqrt \leq \frac \sqrt\,.$

Note that $\sqrt$ is the largest eigenvalue of $G$.

Proofs

Proof of First Statement

Let $A_G$ be the adjacency matrix of $G$ and let $\lambda_1\geq\cdots\geq\lambda_n$ be the eigenvalues of $A_G$ (these eigenvalues are real because $A_G$ is symmetric). We know that $\lambda_1=d$ with corresponding eigenvector $v_1=\frac 1\mathbf$, the normalization of the all-1's vector. Define $\lambda=\sqrt$ and note that $\max\\leq\lambda^2\leq\lambda_1^2=d^2$. Because $A_G$ is symmetric, we can pick eigenvectors $v_2,\ldots,v_n$ of $A_G$ corresponding to eigenvalues $\lambda_2,\ldots,\lambda_n$ so that $\$ forms an orthonormal basis of $\mathbf R^n$.

Let $J$ be the $n\times n$ matrix of all 1's. Note that $v_1$ is an eigenvector of $J$ with eigenvalue $n$ and each other $v_i$, being perpendicular to $v_1=\mathbf$, is an eigenvector of $J$ with eigenvalue 0. For a vertex subset $U \subseteq V$, let $1_U$ be the column vector with $v^\text$ coordinate equal to 1 if $v\in U$ and 0 otherwise. Then,

:$\left, e(S,T)-\frac dn, S, , T, \=\left, 1_S^\operatorname\left(A_G-\frac dnJ\right)1_T\$.

Let $M=A_G-\frac dnJ$. Because $A_G$ and $J$ share eigenvectors, the eigenvalues of $M$ are $0,\lambda_2,\ldots,\lambda_n$. By the Cauchy-Schwarz inequality, we have that $, 1_S^\operatornameM1_T, =, 1_S\cdot M1_T, \leq\, 1_S\, \, M1_T\,$. Furthermore, because $M$ is self-adjoint, we can write

:$\, M1_T\, ^2=\langle M1_T,M1_T\rangle=\langle 1_T,M^21_T\rangle=\left\langle 1_T,\sum_^nM^2\langle 1_T,v_i\rangle v_i\right\rangle=\sum_^n\lambda_i^2\langle 1_T,v_i\rangle^2\leq\lambda^2\, 1_T\, ^2$.

This implies that $\, M1_T\, \leq\lambda\, 1_T\,$ and $\left, e(S,T)-\frac dn, S, , T, \\leq\lambda\, 1_S\, \, 1_T\, =\lambda\sqrt$.

Proof Sketch of Tighter Bound

To show the tighter bound above, we instead consider the vectors $1_S-\fracn\mathbf 1$ and $1_T-\fracn\mathbf 1$, which are both perpendicular to $v_1$. We can expand

:$1_S^\operatornameA_G1_T=\left(\fracn\mathbf 1\right)^\operatornameA_G\left(\fracn\mathbf 1\right)+\left(1_S-\fracn\mathbf 1\right)^\operatornameA_G\left(1_T-\fracn\mathbf 1\right)$

because the other two terms of the expansion are zero. The first term is equal to $\frac\mathbf 1^\operatornameA_G\mathbf 1=\frac dn, S, , T,$, so we find that

:$\left, e(S,T)-\frac dn, S, , T, \ \leq\left, \left(1_S-\fracn\mathbf 1\right)^\operatornameA_G\left(1_T-\fracn\mathbf 1\right)\$

We can bound the right hand side by $\lambda\left\, 1_S-\frac\mathbf 1\right\, \left\, 1_T-\frac\mathbf 1\right\, =\lambda\sqrt$ using the same methods as in the earlier proof.

Applications

The expander mixing lemma can be used to upper bound the size of an independent set within a graph. In particular, the size of an independent set in an $(n, d, \lambda)$-graph is at most $\lambda n/d.$ This is proved by letting $T=S$ in the statement above and using the fact that $e(S,S)=0.$

An additional consequence is that, if $G$ is an $(n, d, \lambda)$-graph, then its chromatic number $\chi(G)$ is at least $d/\lambda.$ This is because, in a valid graph coloring, the set of vertices of a given color is an independent set. By the above fact, each independent set has size at most $\lambda n/d,$ so at least $d/\lambda$ such sets are needed to cover all of the vertices.

A second application of the expander mixing lemma is to provide an upper bound on the maximum possible size of an independent set within a polarity graph. Given a finite projective plane $\pi$ with a polarity $\perp,$ the polarity graph is a graph where the vertices are the points a of $\pi$, and vertices $x$ and $y$ are connected if and only if $x\in y^.$ In particular, if $\pi$ has order $q,$ then the expander mixing lemma can show that an independent set in the polarity graph can have size at most $q^ - q + 2q^ - 1,$ a bound proved by Hobart and Williford.

Converse

Bilu and Linial showedExpander mixing lemma converse
/ref> that a converse holds as well: if a $d$-regular graph $G = (V, E)$ satisfies that for any two subsets $S, T \subseteq V$ with $S \cap T = \empty$ we have

:$\left, e(S, T) - \frac\ \leq \lambda \sqrt,$

then its second-largest (in absolute value) eigenvalue is bounded by $O(\lambda (1+\log(d/\lambda)))$.

Generalization to hypergraphs

Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.

Let $H$ be a $k$-uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of $k$ vertices. For any choice of subsets $V_1, ..., V_k$ of vertices,

:$\left, , e(V_1,...,V_k), - \frac, V_1, ..., V_k, \ \le \lambda_2(H)\sqrt.$

Notes

References

*.
*F.C. Bussemaker, D.M. Cvetković, J.J. Seidel. Graphs related to exceptional root systems, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), volume 18 of Colloq. Math. Soc. János Bolyai (1978), 185-191.

*
*.

*.

*{{citation
, last1 = Friedman , first1 = J.
, last2 = Widgerson , first2 = A.
, journal = Combinatorica
, pages = 43–65
, title = On the second eigenvalue of hypergraphs
, volume = 15
, issue = 1
, year = 1995
, url = https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/FW95/fw95a.pdf
, doi = 10.1007/BF01294459, s2cid = 17896683
.

Theoretical computer science
Lemmas in graph theory
Algebraic graph theory